/*
 * @lc app=leetcode.cn id=21 lang=cpp
 *
 * [21] 合并两个有序链表
 */
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
// @lc code=start
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution
{
  public:
    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        if (!list1 || !list2) {
            return list1 ? list1 : list2;
        }
        ListNode *new_head = new ListNode;
        ListNode *tmp = new_head;
        ListNode *tmp1 = list1;
        ListNode *tmp2 = list2;

        while (tmp1 && tmp2) {
            if (tmp1->val <= tmp2->val) {
                tmp->next = tmp1;
                tmp1 = tmp1->next;
                tmp = tmp->next;
            } else {
                tmp->next = tmp2;
                tmp2 = tmp2->next;
                tmp = tmp->next;
            }
        }

        if (tmp1) {
            tmp->next = tmp1;
        }

        if (tmp2) {
            tmp->next = tmp2;
        }

        return new_head->next;
    }
};
// @lc code=end
